Greedy Algorithm (গ্রিডি অ্যালগরিদম) একটি সমস্যা সমাধানের কৌশল যা প্রতিটি ধাপে সর্বোত্তম বা গ্রিডি বিকল্প নির্বাচন করে, যার লক্ষ্য থাকে স্থানীয়ভাবে সবচেয়ে ভালো ফলাফল পাওয়া। এই পদ্ধতিতে, অ্যালগরিদম সমস্যাটির জন্য সেরা সমাধান খুঁজে বের করার চেষ্টা করে, কিন্তু এটি সম্পূর্ণ সমাধান অর্জনের জন্য পর্যায়ক্রমে একাধিক স্থানীয় সিদ্ধান্ত নেয়। গ্রিডি অ্যালগরিদম সাধারণত সময় সাশ্রয়ী এবং কার্যকরী, তবে এটি সবসময় সঠিক সমাধান দেয় না।
Greedy Algorithm এর ধারণা
গ্রিডি অ্যালগরিদম মূলত স্থানীয়ভাবে সবচেয়ে ভালো সমাধান বেছে নেয়ার পদ্ধতি অনুসরণ করে, তবে পুরো সমস্যা সমাধান করার সময় কিছু বৈশিষ্ট্য রাখতে হয়। এটি সম্পূর্ণ সমাধান অর্জনের জন্য প্রতিটি ধাপে একটি সিদ্ধান্ত নেয় এবং সেই সিদ্ধান্তটি তখনই চূড়ান্ত করে ফেলে, পরবর্তী কোনো সিদ্ধান্ত গ্রহণ করার আগে।
Greedy Algorithm এর প্রধান বৈশিষ্ট্য:
- নির্দিষ্ট সিদ্ধান্ত গ্রহণ: প্রতি পদক্ষেপে একটি নির্দিষ্ট সিদ্ধান্ত নেয়া হয়।
- স্থানীয় অপ্টিমাইজেশন: একে একে স্থানীয়ভাবে সবচেয়ে ভালো বিকল্প বেছে নেয়া হয়।
- তাত্ক্ষণিক সমাধান: দ্রুত সমাধান পাওয়ার জন্য এটি একে একে সিদ্ধান্ত নেয় এবং শেষ পর্যন্ত একটি বৃহত্তর সমাধানে পৌঁছায়।
এটি সাধারণত সেই ধরনের সমস্যাগুলোর জন্য কার্যকরী, যেখানে স্থানীয়ভাবে সেরা সিদ্ধান্ত নেওয়া পুরো সমাধানকে সঠিকভাবে নির্মাণ করতে সহায়তা করে। তবে, সব সমস্যার জন্য গ্রিডি অ্যালগরিদম সর্বদা সঠিক সমাধান দেয় না।
Greedy Algorithm এর উদাহরণ
1. Activity Selection Problem (অ্যাকটিভিটি সিলেকশন সমস্যা)
এটি একটি ক্লাসিক গ্রিডি অ্যালগরিদমের উদাহরণ, যেখানে বিভিন্ন সময়ের জন্য বিভিন্ন কার্যক্রম দেওয়া থাকে এবং লক্ষ্য থাকে সবচেয়ে বেশি কার্যক্রমে অংশগ্রহণ করা, যেগুলি একে অপরের সাথে ওভারল্যাপ না করে।
সমস্যা:
ধরা যাক, আমাদের কাছে কিছু কার্যক্রম রয়েছে যেগুলোর শুরুর এবং শেষের সময় দেওয়া আছে। আমাদের লক্ষ্য হলো, যতগুলো কার্যক্রম একে অপরের সাথে সংঘর্ষ (overlap) না করে সেগুলো সম্পাদন করা।
সমাধান:
গ্রিডি অ্যালগরিদমে, আমরা প্রতিটি কার্যক্রমের শেষে সময়ের ভিত্তিতে সিদ্ধান্ত নেবো এবং যতগুলো কার্যক্রম আগে সম্পন্ন হয়েছে তাদের মধ্যে সময়ের সঙ্গে সবচেয়ে ছোটটি বেছে নেবো।
উদাহরণ কোড:
import java.util.*;
public class ActivitySelection {
// Activity class to store start and end time of an activity
static class Activity {
int start, end;
public Activity(int start, int end) {
this.start = start;
this.end = end;
}
}
// Function to perform Activity Selection using Greedy Algorithm
public static void activitySelection(Activity[] activities) {
// Sort activities by their end time
Arrays.sort(activities, (a, b) -> a.end - b.end);
// The first activity always gets selected
int lastSelected = 0;
System.out.println("Selected Activity: " + "Start: " + activities[lastSelected].start + " End: " + activities[lastSelected].end);
// Consider the rest of the activities
for (int i = 1; i < activities.length; i++) {
if (activities[i].start >= activities[lastSelected].end) {
// If activity start time is greater than or equal to the last selected activity's end time, select it
System.out.println("Selected Activity: " + "Start: " + activities[i].start + " End: " + activities[i].end);
lastSelected = i;
}
}
}
public static void main(String[] args) {
Activity[] activities = {
new Activity(1, 3),
new Activity(2, 5),
new Activity(4, 7),
new Activity(1, 8),
new Activity(5, 9),
new Activity(8, 10)
};
activitySelection(activities); // Call function to select activities
}
}
আউটপুট:
Selected Activity: Start: 1 End: 3
Selected Activity: Start: 4 End: 7
Selected Activity: Start: 8 End: 10
এখানে, প্রতিটি কার্যক্রমের শেষ সময়ের ভিত্তিতে আমরা সিদ্ধান্ত নিয়েছি যে কোন কার্যক্রম গ্রহণ করা হবে, যাতে সর্বাধিক কার্যক্রম নির্বাচন করা যায়।
Greedy Algorithm এর অন্যান্য উদাহরণ
2. Fractional Knapsack Problem
এটি একটি সাধারণ গ্রিডি সমস্যা যেখানে আমাদের লক্ষ্য একটি নির্দিষ্ট ওজনের কনটেইনারে (ন্যাকস্যাক) সর্বাধিক মূল্যবান বস্তু সংরক্ষণ করা। এখানে, গ্রিডি অ্যালগরিদমে সবচেয়ে বেশি মূল্যবান বস্তু প্রথমে নির্বাচিত হয়, যা সর্বাধিক মূল্য পাওয়া যায়।
3. Huffman Coding
হাফম্যান কোডিং গ্রিডি অ্যালগরিদমের আরেকটি উদাহরণ, যা ডেটা সংকোচনের জন্য ব্যবহৃত হয়। এটি একটি বাইট বা স্ট্রিংয়ের সর্বাধিক পুনরাবৃত্তি হওয়া অক্ষরগুলিকে ছোট কোডে সংকুচিত করতে সাহায্য করে।
4. Job Sequencing Problem
এটি এমন একটি সমস্যা যেখানে বিভিন্ন কাজের জন্য নির্দিষ্ট সময় দেওয়া থাকে এবং আমাদের লক্ষ্য থাকে, যতগুলো কাজ করা সম্ভব, তাদের মধ্যে মুনাফা সর্বাধিক করা।
Greedy Algorithm এর সুবিধা এবং সীমাবদ্ধতা
সুবিধা:
- দ্রুত সমাধান: গ্রিডি অ্যালগরিদম সাধারণত দ্রুত কাজ করে এবং কম সময়ে সমাধান দেয়।
- সহজ বাস্তবায়ন: এটি প্রোগ্রামিংয়ের জন্য তুলনামূলকভাবে সহজ।
- স্মৃতি সাশ্রয়ী: অনেক ক্ষেত্রে গ্রিডি অ্যালগরিদমে অতিরিক্ত স্টোরেজের প্রয়োজন হয় না।
সীমাবদ্ধতা:
- সঠিক সমাধান নাও দিতে পারে: কিছু সমস্যায় গ্রিডি অ্যালগরিদম সঠিক সমাধান নাও দিতে পারে, বিশেষত যখন এটি স্থানীয়ভাবে সেরা সিদ্ধান্ত নেয়, তবে পূর্ণ সমস্যায় এটি সর্বোত্তম সিদ্ধান্ত না হয়।
- সব ধরনের সমস্যায় কার্যকরী নয়: এটি শুধুমাত্র সেই ধরনের সমস্যায় কার্যকরী যেখানে স্থানীয় অপ্টিমাইজেশন পুরো সমস্যার জন্য কার্যকর।
সারাংশ
Greedy Algorithm (গ্রিডি অ্যালগরিদম) একটি সমস্যা সমাধানের কৌশল যা প্রতিটি ধাপে সবচেয়ে ভালো সিদ্ধান্ত নেয়ার চেষ্টা করে, যার লক্ষ্য থাকে দ্রুত সমাধান পাওয়া। এটি সাধারণত স্থানীয়ভাবে সেরা সিদ্ধান্ত নেয় এবং কখনো কখনো পুরো সমস্যা সমাধানে সঠিক ফলাফল দেয়। এটি Activity Selection Problem, Fractional Knapsack, Job Sequencing, Huffman Coding ইত্যাদি সমস্যায় ব্যবহৃত হয়। তবে, সব সমস্যায় গ্রিডি অ্যালগরিদম সর্বোত্তম সমাধান দেয় না, এবং এটি সঠিক ফলাফল নিশ্চিত করার জন্য নির্দিষ্ট প্রকারের সমস্যায় প্রয়োগ করা উচিত।
Read more
